2384. Largest Palindromic Number

题目 2384. Largest Palindromic Number

思路分析

代码实现

import java.util.HashMap;

class Solution {
    public String largestPalindromic(String num) {
        HashMap<Character, Integer> map = new HashMap<>();
        char[] chars = num.toCharArray();

        for (char c : chars) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        StringBuilder left = new StringBuilder();
        String mid = "";

        for (char c = '9'; c >= '0'; c--) {
            if (!map.containsKey(c)) continue;

            int count = map.get(c);

            // --- 处理成对的数 (放在两边) ---
            // 只有当数字不是 '0'，或者左边已经有非0数字时，才能放 '0'
            if (c != '0' || left.length() > 0) {
                // 把能凑成对的都放进左半边
                while (count >= 2) {
                    left.append(c);
                    count -= 2;
                }
            } else {
                // 如果是 '0' 且是前导零 (left为空)，不能放入 left，但可能留作中间数
                // 这里不做操作，count 保持不变，留给下面判断 mid
            }

            // --- 处理剩下的单个值 (放在中间) ---
            // 因为我们是从 9 到 0 遍历的，第一个遇到的剩余单数一定是最大的
            // 只有当 mid 还没被填过时，才填入
            if (count > 0 && mid.equals("")) {
                mid = String.valueOf(c);
            }
        }

        // 3. 边界特判
        // 如果左边没东西，中间也没东西 (比如输入是空的，虽不仅限于此)，或者是 "0" 的情况
        if (left.length() == 0 && mid.equals("")) {
            return "0"; // 至少要返回一个 0
        }

        // 4. 拼接：左 + 中 + 右(左的反转)
        return left.toString() + mid + left.reverse().toString();
    }
}

数据仅在0~9 无需hash 直接数组做bitmap计数即可

 class Solution {
    public String largestPalindromic(String num) {
        int[] counts = new int[10];
        for(char c:num.toCharArray()){
            counts[c-'0']++;
        }

        StringBuilder leftHalf = new StringBuilder();

        for(int i=9;i>=0;i--){
            if(i==0 && leftHalf.length()==0){
                continue;
            }
            while(counts[i]>1){
                leftHalf.append(i);
                counts[i]-=2;
            }
        }

        String mid = "";
        for(int i=9;i>=0;i--){
            if(counts[i]>0){
                mid=String.valueOf(i);
                break;
            }
        }

        if (leftHalf.length() == 0 && mid.equals("")) {
            return "0";
        }

        return leftHalf.toString() + mid + leftHalf.reverse().toString();
    }
}

同类题型

视频讲解